Java性能：Java逻辑从巨大的列表中找到最高的3个数字

Question

这是我在一次面试中被问到的关于检查绩效知识的问题

问题-我有一个整数列表（默认情况下是Arraylist，如果你想更改列表，那么请调整）。 有数百万个条目具有随机的int值。 值可以重复

从这个列表中，我需要在下面的案例中找到3个最高的唯一数字

1）时间有限时（时效性） 2） 内存有限时（内存有效）

我试图回答这些问题，但没有找到有效的解决办法。 我的解决方案是使用流API， 然后使用distinct（）获得唯一的数字 Sort（）对列表进行排序 然后在收集后显示前三名

然而，他们说你不需要排序。 我想用3个变量来保存前3个值。 然后我反复浏览列表，检查前三名中的当前值是否有更高的值？如果不是，我就交换

然而，这里有很多比较，因此在每次迭代中，我们必须进行这些比较

有谁能告诉我解决这个问题的更好方法吗

此外，如果有人能提供一些链接/描述/方法来解决与性能相关的问题，我将非常感激

编辑：需要输出前三个唯一值

Answer 1

如果没有任何空间限制，那么一个选项可能是将列表集合添加到Java TreeSet：

List<Integer> list = new ArrayList<>();
// populate the above list
TreeSet<Integer> set = new TreeSet<>(list);
set = (TreeSet<Integer>)set.descendingSet();

列表中的每个条目都将被放置在TreeSet后面的红黑树中，重复项将被自动删除。我调用上面的TreeSet#descendingSet，为我们提供一个排序集，默认情况下它将按降序迭代

现在只需迭代前三个条目：

int count = 0;
Iterator<Integer> iterator = set.iterator();
    while(iterator.hasNext() && count < 3) {
    System.out.println("Value #" + count + " = " + iterator.next());
    ++count;
}

至于内存有限的方法，您可能不得不求助于某种就地排序算法，它要么只使用原始数据结构，要么只使用一点额外的数据结构。我对此类解决方案几乎没有专业知识，所以除了我刚才提到的以外，我不会尝试任何其他方法